import java.awt.List;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

public class driver {
	public driver() {
	}

	private String input;

	public Set<String> nextStates(String s) {
		input = s;
		Set<String> output = new TreeSet<String>();
		// Rule 1

		// Rule!1:!If!your!string!ends!in!an!I,!you!can!add!a!U on!the!end:! xI

		if (input.charAt(input.length() - 1) == 'I') {
			output.add(input + "U");
		}

		// Rule 2
		// If!the!string!starts!with M,!you!can!double!what!comes!after!the!M:
		// Mx Mxx
		// If Substring[first] == M then substring[1,end] added to end
		if (input.charAt(0) == 'M') {
			output.add("M" + input.substring(1) + input.substring(1));
		}
		// Rule 3
		// !If!you!have!III in!a!string,!you!can!replace!it!with!a!U:
		// If substring.contains III then substring = u
		if (input.contains("III")) {
			for (int i = 1; i < input.length() - 2; i++) {

				if (input.charAt(i) == 'I') {

					String temp = input.substring(i, i + 3);

					if (temp.equals("III")) {
						output.add(input.substring(0, i) + "U"
								+ input.substring(i + 3, input.length()));
					}
				}
			}
		}

		// Rule 4
		// Rule!4:!If!you!have!UU in!a!string,!you!can!delete!it!altogether:
		// If substring contains UU, substring =''
		if (input.contains("UU")) {
			for (int i = 1; i < input.length() - 1; i++) {

				if (input.charAt(i) == 'U') {

					String temp = input.substring(i, i + 2);

					if (temp.equals("UU")) {
						output.add(input.substring(0, i)
								+ input.substring(i + 2, input.length()));
					}
				}
			}
		}

		return output;
	}

	public boolean BreaddthFirstSearch(String s) {
		Queue<String> q = new LinkedList<String>();
		this.input = "MI";
		int count = 0;
		boolean found = false;

		q.add(input);

		while (found == false) {
			// System.out.println("peek" + q.peek());
			if (q.peek().equals(s)) {
				found = true;
				System.out.println(q.peek() + " Found at Iteration :" + count
						+ " queue :" + q.size());
				System.out.println("queue" + q);

			} else
				q.addAll(nextStates(q.peek()));
			q.poll();
			count++;

		}
		return found;

	}

	public boolean DepthFirstSearch(String s) {
		Stack<String> q = new Stack<String>();
		this.input = "MI";
		int count = 0;
		int n =4;
		boolean found = false;

		q.add(input);

		while (found == false) {
			System.out.println("peek" + q.peek());
			if (q.peek().equals(s)) {
				found = true;
				System.out.println("queue" + q);
				System.out.println();
				System.out.println(q.peek() + "Found at Iteration :" + count
						+ " queue :" + q.size());

			} else {
				if(count <= n){
				String temp = q.peek();
				System.out.println("temp = " + q.peek());
				q.pop();
				System.out.println("popped");
				q.addAll(nextStates(temp));
				System.out.println("Added" + nextStates(temp));

				temp = null;

				count++;
				}
				else{
					q.pop();
					count--;
				}
			}
			if ((count > 3) && (q.isEmpty())) {
				System.out.println("reached "+ n +" iterations and not found");
				found = false; // ie stop
			}

		}
		return found;
	}
	public boolean DepthLimitedSearch(String s,int n) {
		Stack<String> q = new Stack<String>();
		this.input = "MI";
		int count = 0;
		boolean found = false;

		q.add(input);

		while (found == false) {
			System.out.println("peek" + q.peek());
			if (q.peek().equals(s)) {
				found = true;
				System.out.println("queue" + q);
				System.out.println();
				System.out.println(q.peek() + "Found at Iteration :" + count
						+ " queue :" + q.size());

			} else {
				String temp = q.peek();
				q.pop();
				q.addAll(nextStates(temp));

				temp = null;

				count++;
			}
			if (count >= n) {
				System.out.println("reached " +n + " iterations and not found");
				found = false; 
				break;
				
			}

		}
		return found;
	}
	
	public boolean iterativeDeepeningSearch (String s){
		int n = 0;
		Boolean found = false;
		
		while(!found){
			if (DepthLimitedSearch(s, n) == true){
				System.out.println("Found :" + s + ", n= " + n);
				found = true; 
			}
			else{
				n++;
			}
		}
		return found;
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
}
